#ifndef __BPTREE_H__
#define __BPTREE_H__

#define VERSION			0.1
#define DEFAULT_ORDER	4
#define MIN_ORDER		3
#define MAX_ORDER		20
#define TRUE			1
#define FALSE			0

struct Record;
typedef struct Record* pRecord;

struct TreeNode;
typedef struct TreeNode* pNode;
typedef struct TreeNode node;

/* utility */
int hash(pRecord rec);
void printLeaves(pNode root );
void printOneLeaf(pNode leaf);
void printOneNode(pNode node);
pNode findLeaf(pNode root, int key);
pNode find(pNode root, int key);

// start a new tree, and insert a element
pNode insertLeafAfterSplit(pNode root, pNode leaf, pRecord rec);

/* insert */
pNode makeNode(void);
pNode makeLeaf(void);
pRecord makeRecord(char* s);
pNode insert(pNode root, pRecord rec);
pNode insertLeaf_full(pNode root, pNode leaf, int key, pRecord rec);
pNode insertLeaf_notFull(pNode root, pNode leaf, int key, pRecord rec);
pNode insertParent(pNode root, pNode left, int  midKey, pNode right);
pNode insertIntoNewRoot(pNode leaf, int  midKey, pNode right);
pNode insertNode_full(pNode root, pNode node, int key, pNode freeNode);
pNode insertNode_notFull(pNode root, pNode node, int key, pNode freeNode) ;
pNode startNewTree(int key, pRecord rec);

/* delete */
pNode delete(pNode root, pRecord rec);
pNode delete_fromNode(pNode root, pNode Node, pNode target);
pNode borrowFromSibling(pNode root, pNode node, int isLeft);
pNode merge(pNode root, pNode node, int isLeft);
// pNode deleteLeaf_merge(pNode root, pNode leaf, int key);
#endif